class Solution
{
    string t;
    vector<int> f;
public:
    int dfs(int i)
    {
        if (i < 0) return 0;//终止条件  这里有两种可能，一种是更新过答案的反季，另一种是一次答案也没更新的返回
        if (f[i] != -1) return f[i];//说明之前来过了 直接返回

        int ans = 0x3f3f3f3f;
        int mxCnt = 0;//最大出现次数
        int cnt[26] = { 0 };
        int k = 0;//出现的字母种类
        for (int j = i; j >= 0; j--)
        {
            k += cnt[t[j] - 'a']++ == 0 ? 1 : 0;
            mxCnt = max(cnt[t[j] - 'a'], mxCnt);
            if (k * mxCnt == i - j + 1)//种类乘以最大出现个数等于当前窗口长度 这里就限定住了每个数量都是相等的
                ans = min(ans, dfs(j - 1) + 1);
        }
        return f[i] = ans;//记忆化并且返回答案  这里因为会先递到最深处，所以记忆化是从下标小的地方开始的
    }
    int minimumSubstringsInPartition(string s)
    {
        t = s;
        int n = s.size();
        f.resize(n, -1);
        return dfs(n - 1);//从后往前
    }
};